home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / edge_array.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  3.0 KB  |  81 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.7 Node and edge arrays (node\_array, edge\_array)}
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $A$ of the parameterized data type $node\_array\<E\>$ 
  8. ($edge\_array\<E\>$) is a partial mapping from the node set (edge set) 
  9. of a (u)graph $G$ to the set of variables of data type $E$, called the 
  10. element type of the array. The domain $I$ of $A$ is called the index set 
  11. of $A$ and $A(x)$ is called the element at position $x$. $A$ is said to 
  12. be valid for all nodes (edges) in $I$. 
  13.  
  14. \def\name {$node/edge\_array\<E\>$}
  15. \def\type {$node/edge\_array$}
  16.  
  17. \bigskip
  18. {\bf 2. Creation}
  19.  
  20. a) \create A {}
  21.  
  22. b) \create A (graph\ G)
  23.  
  24. c) \create A (graph\ G,\ E\ x)
  25.  
  26. d) \create A (graph\ G,\ int\ n,\ E\ x)    
  27.  
  28.  
  29. creates an instance $A$ of type $node\_array(E)$ or $edge\_array(E)$. Variant a)
  30. initializes the index set of $A$ to the empty set, Variants b) and c) 
  31. initialize the index set of $A$ to be the entire node (edge) set of graph $G$,
  32. i.e., $A$ is made valid for all nodes (edges) currently contained in $G$. 
  33. Variant c) in addition initializes $A(i)$ with $x$ for all nodes (edges) 
  34. $i$ of $G$. Variant d) makes $A$ a $node/edge\_array(E)$ valid for up to $n$ 
  35. nodes/edges of $G$, \precond $n \ge |V|$ ($|E|$), this is useful if you want
  36. to use the array for later inserted nodes/edges.
  37.  
  38.  
  39.  
  40. \bigskip
  41. \def\var{$A$}
  42. {\bf 3. Operations}
  43. \medskip
  44.  
  45. \+\op void  init {graph\ G}         
  46.                              {sets the index set $I$ of $A$ to the node (edge)}
  47. \+\nop                       {set of $G$, i.e., makes $A$ valid for all nodes}
  48. \+\nop                       {(edges) of $G$.}
  49. \smallskip
  50. \+\op void  init {graph\ G,\ E\ x}    
  51.                              {makes $A$ valid for all nodes (edges) of $G$ }
  52. \+\nop                       {and sets $A(i) = x$ for all nodes (edges) of $G$}
  53. \smallskip
  54. \+\op void  init {graph\ G,\ int\ n,\ E\ x}  {}
  55. \+\nop                       {makes $A$ valid for at most $n$ nodes (edges)}
  56. \+\nop                       {of $G$ and sets $A(i) = x$ for all nodes (edges)}
  57. \+\nop                       {of $G$. \precond $n \ge |V|$ ($n \ge |E|$). }
  58. \smallskip
  59. \+\opa E\&  {node/edge\ i}                    
  60.                              {access the variable $A(i)$.}
  61. \+\nop                       {\precond $A$ must be valid for $i$.}
  62.  
  63. \bigskip
  64. {\bf 4. Implementation}
  65.  
  66. Node (edge) arrays for a graph $G$ are implemented by \CC vectors and an 
  67. internal numbering of the nodes and edges of $G$. The access operation 
  68. takes constant time, $init$ takes time $O(n)$, where $n$ is the number of 
  69. nodes (edges) currently in $G$. The space requirement is $O(n)$.
  70.  
  71. {\bf Remark}: A node (edge) array is only valid for a bounded number of
  72. the nodes (edges) contained in $G$. This number is either the total number
  73. of nodes of $G$ at the moment of the array creation (variants a) \dots c)) or 
  74. it is explicitely set by the user (variant d)).  Access operations for 
  75. additional later added nodes (edges) are not allowed. Fully dynamic node and
  76. edge arrays can be realized by using hashing arrays, e.g., 
  77. $h\_array(node,\dots)$ (cf.~section~4.5).
  78.  
  79. \vfill\eject
  80.  
  81.